#ifndef SOLUTION_H_
#define SOLUTION_H_
#include <algorithm>

using namespace std;

class Solution {
public:
    int maxSubArray(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
		if(n<=0)
			return 0;
		if(n==1)
			return A[0];

        int maxSum = 0, maxEH = 0;
		for(int i=0;i<n;i++)
		{
			maxEH += A[i];
			if(maxEH < 0)
				maxEH=0;
			maxSum = max(maxSum,maxEH);
		}

		if(maxSum<=0)
		{
			maxSum = A[0];
			for(int i=1;i<n;i++)
				maxSum = max(maxSum,A[i]);
		}

		return maxSum;
    }
};
#endif